package gmat.test

import gmat.intr.Matrix
import gmat.impl.MatrixJC


public class ID3{
	final static all = Matrix.all
	final static inf = Double.POSITIVE_INFINITY
	final static eps = Double.MIN_VALUE
	
	def useTree(Matrix patterns, List indices, Tree tree, int nBins, List uc){
		def targets = MatrixJC.zeros(patterns.size(1))
		
		if(indices.isEmpty()){
			return targets
		}
		
		if(patterns.size(0) == 1 || tree.split_dim == 0){
			def rand = new Random()
			
			for(i in 0..nBins-1){
				List id = indices.findAll({ patterns[it].val() == i })
				if(!id.isEmpty()){
					if(tree.child[i] != inf){
						targets[id] = tree.child[i]
					} else{
						targets[id] = uc[rand(uc.size())]
					}
				}
			}
			return targets
		}
		
		int dim = tree.split_dim
		List dims = (0..patterns.size(0)-1).toList - dim
		
		for(i in 0..nBins-1){
			List id = indices[patterns[dim, indices].find(i)]
			targets = targets + useTree(patterns[dims, all], id, tree.child[i], nBins, uc)
		}
		return targets
	}
	
	def makeTree(Matrix patterns, Matrix targets, int incNode, int nBins){
		Tree tree
		int ni = patterns.size(0)
		int l = patterns.size(1)
		List uc = targets.unique()
		
		if(ni == 1 || incNode > l){
			for(i in 0..nBins-1){
				tree.split_dim = 0
				if(!targets.isEmpty()){
					List indices = targets.find(i)
					if(!indices.isEmpty()){
						if((targets >> indices).unique().size() == 1){
							tree.child[i] = targets[indices.first()]
						} else{
							def filter = targets >> indices
							def hist = MatrixJC.zeros(uc.size())
							(0..uc.size()-1).each({ hist[it] = filter.count(uc[it]) })
							tree.child[i] = uc[hist.maxIndex()]
						}
					} else{
						tree.child[i] = inf
					}
				} else{
					tree.child[i] = inf
				}
			}
			return tree
		}
		
		def pNode = MatrixJC.zeros(uc.size())
		(0..uc.size()-1).each({ pNode[it] = targets.count(uc[it]) / l })
		def iNode = (pNode.log() * pNode).sumAll() * -1/Math.log(2)
		
		def deltaIb = MatrixJC.zeros(ni)
		def p = MatrixJC.zeros(uc.size(), nBins)
		
		for(i in 0..ni-1){
			for(j in 0..uc.size()-1){
				for(k in 0..nBins-1){
					p[j,k] = patterns[i,targets.find(uc[j])].count(k)
				}
			}
			def pK = p.sum()
			p = p / l
			pK = pK / (pK.sumAll())
			def info = ((p + eps).log() * p).sum() * (-1/Math.log(2))
			deltaIb[i] = -Math.log(2) * (iNode - (pK * info).sumAll()) / ((pK + eps).log() * pK).sumAll()
		}
		
		int dim = deltaIb.maxIndex()
		
		tree.split_dim = dim
		List dims = (0..ni-1).toList() - dim
		for(i in 0..nBins-1){
			def indices = patterns[dim, all].find(i)
			tree.child[i] = makeTree(patterns[dims, indices], targets >> indices, incNode, nBins)
		}
		
		return tree
	}
}
